package LeetCode.Leet200_299.Leet270_279.Leet279;

/**
 * @ClassName Solution_1
 * @Author 孙天赐
 * @Date 2025/10/2 8:25
 * @Description TODO: 方法一   动态规划 31ms 61.37%
 */
class Solution_1 {
    public int numSquares(int n) {
        // 第i次循环，dp[j]的含义为：小于等于i^2的完全平方数，组成j的最小数量为dp[j]
        int[] dp = new int[n + 1];

        // 初始化为最大值（0除外）
        for (int j = 1; j <= n; j++) {
            dp[j] = Integer.MAX_VALUE;
        }

        // 动态规划
        for (int i = 1; i * i <= n; i++) {
            int num = i * i;
            // 注意j从num开始，所以对于j<num的情况，dp[j]肯定是保持不变的
            for (int j = num; j <= n; j++) {
                // 两者取较小值
                // 1.不包含完全平方数num，即为dp[j]
                // 2.包含完全平方数num，即为dp[j - num] + 1
                dp[j] = Math.min(dp[j], dp[j - num] + 1);
            }
        }

        return dp[n];
    }
}
